package 算法.树;

import testJ.S;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class N叉树的前序遍历 {
    public static void main(String[] args) {
        Node no1 = new Node(1);
        Node no2 = new Node(2);
        Node no3 = new Node(3);
        Node no4 = new Node(4);
        Node no5 = new Node(5);
        Node no6 = new Node(6);

        no3.children.add(no5);
        no3.children.add(no6);

        no1.children.add(no3);
        no1.children.add(no2);
        no1.children.add(no4);


        preorder(null).forEach(e->{
            System.out.println(e);
        });

    }
    public static List<Integer> preorder1(Node root) {
        List<Integer> list = new ArrayList<>();

        list.add(root.val);
        if(root.children.size() < 1) return list;
        for (Node child : root.children) {
            list.addAll(preorder1(child));
        }

        return list;
    }
    public static List<Integer> preorder(Node root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;
        Stack<Node> stack = new Stack();
        stack.push(root);

        Node temp;
        while (true){
            if(stack.isEmpty()) return list;

            temp = stack.pop();
            list.add(temp.val);
            for (int i = temp.children.size() - 1; i >= 0; i--) {
                stack.push(temp.children.get(i));
            }
        }
    }

}
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
        children = new ArrayList<>();
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
